#include<iostream> 
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;

int t ,h,i ,j ,k ,l ;
char s1[50001],s2[50001];

int main()
{
    cin>>t;
    for( i =1;i<=t;i++)
    {
        memset( s1 , 0 ,sizeof(s1) ) ;
        memset( s2 , 0 ,sizeof(s2) ) ;
        cin>>s1>>s2;
        int min = strlen(s2);
        int count;
        for( j=0 ; j<strlen(s1)-strlen(s2)+1; j++ ) 
        {
          count = 0 ;
          for( k = 0 ; k < strlen(s2) ; k++ )
          {
              if( s2[k] != s1[j+k] )     count++;
          }
          if( count < min ) min = count;
        }
        printf("Case #%d: %d\n",i,min);
    }
    //system("pause");
    return 0;
}
